import java.util.Arrays;
public class mergeSort {
    public  static  void main(String args[]) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 实现归并排序
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length <2) {
            return;
        }
        process(arr, 0, arr.length-1);
    }
    public  static void process(int[] arr,int L,int R) {
        if(L == R) { // arr[L...R]范围只有一个数，直接返回， base case
            return ;
        }
        int mid = L + ((R-L)>>1); //求中点值
        process(arr, L, mid);
        process(arr,mid+1,R);
        merge(arr, L, mid, R);
    }
    public static void merge(int[] arr,int L,int M, int R) {
        int[] help = new int[R- L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <=M) {
            help[i++] = arr[p1++];
        }
        while (p2 <=R) {
            help[i++] = arr[p2++];
        }
        for(i = 0;i<help.length;i++) {
            arr[L+i] = help[i];
        }
    }
}
